#include "sortAlgorithm.h"

<<<<<<< HEAD:cxx/algorithm/src/sortAlgorithm.cc
void fastsort(std::vector<int>& nums,int left,int right){
    if(left>right)
        return;
    int l=left,r=right;
    int privot = nums[l];
    while (l!=r){
        while (nums[r]>=privot&&l<r)
            r--;
        while (nums[l]<=privot&&l<r)
            l++;
        if(l<r)
            std::swap(nums[l],nums[r]);
    }
    nums[left]=nums[l];
    nums[l]=privot;
    fastsort(nums,left,l-1);
    fastsort(nums,l+1,right);
}

void fastsort1(std::vector<int>& nums,int left,int right){
    if(left>right)
        return;
    int l=left,r=right;
    int privot = nums[l];
    while (l!=r){
        while (nums[r]>=privot&&l<r)
            r--;
        while (nums[l]<=privot&&l<r)
            l++;
        if(l<r)
            std::swap(nums[l],nums[r]);
    }
    nums[left]=nums[l];
    nums[l]=privot;
    fastsort1(nums,left,l-1);
    fastsort1(nums,l+1,right);

=======
void maxHeapify(std::vector<int> &nums, int leaf, int max_index) {
    int large_index;
    for (; (leaf << 1) + 1 <= max_index;) {
        int lson = (leaf << 1) + 1;
        int rson = lson + 1;
        if (lson <= max_index)
            large_index = nums[lson] > nums[leaf] ? lson : leaf;

        if (rson <= max_index)
            large_index = nums[rson] > nums[large_index] ? rson : large_index;

        if (large_index != leaf) {
            std::swap(nums[leaf], nums[large_index]);
            leaf = large_index;
        } else
            break;
    }
}
void buildMaxHeap(std::vector<int> &nums, int max_index) {
    // 调整非叶子节点
    for (int leaf = max_index >> 1; leaf >= 0; --leaf) {
        maxHeapify(nums, leaf, max_index);
    }
}
void heapSort(std::vector<int> &nums) {
    int max_index = static_cast<int>(nums.size()) - 1;
    buildMaxHeap(nums, max_index);
    for (int i = max_index; i >= 1; --i) {
        std::swap(nums[i], nums[0]);
        max_index -= 1;
        maxHeapify(nums, 0, max_index);
    }
}

void fastsort(std::vector<int> &nums, int left, int right) {
    if (left > right)
        return;
    int l = left, r = right;
    int privot = nums[l];
    while (l != r) {
        while (nums[r] >= privot && l < r)
            r--;
        while (nums[l] <= privot && l < r)
            l++;
        if (l < r)
            std::swap(nums[l], nums[r]);
    }
    nums[left] = nums[l];
    nums[l] = privot;
    fastsort(nums, left, l - 1);
    fastsort(nums, l + 1, right);
}

int SelectPrivot(int left, int right) {
    return rand() % (right - left + 1) + left;
}
template <typename T> int Partition(T nums[], int left, int right) {
    int r = SelectPrivot(left, right);
    int l = left - 1;
    std::swap(nums[r], nums[right]);
    for (int r = left; r < right; r++) {
        if (nums[r] < nums[right]) {
            l++;
            if (l != r)
                std::swap(nums[r], nums[l]);
        }
    }
    l++;
    std::swap(nums[l], nums[right]);
    return l;
}
template <typename T> void QuickSort(T array[], int left, int right) {
    if (right <= left)
        return;
    int mid = Partition(array, left, right);
    QuickSort(array, left, mid - 1);
    QuickSort(array, mid + 1, right);
}

void maxHeapifyRec(std::vector<int> &a, int root) {
    int left = (root << 1) + 1;
    int right = left + 1;
    int largest = root;
    if (left <= a.size() && a[left] > a[largest])
        largest = left;
    if (right < a.size() - 1 && a[right] > a[largest])
        largest = right;
    if (largest != root) {
        std::swap(a[largest], a[root]);
        maxHeapifyRec(a, largest);
    }
}

// int SelectPrivot(int left, int right) { return left; }
// template <typename T> int Partition(T nums[], int left, int right) {
//     int l = left, r = right;
//     int privot = SelectPrivot(left, right);
//     while (l != r) {
//         while (nums[r] >= nums[privot] && l < r)
//             r--;
//         while (nums[l] <= nums[privot] && l < r)
//             l++;
//         if (l < r)
//             std::swap(nums[l], nums[r]);
//     }
//     std::swap(nums[privot], nums[l]);
//     return l;
// }
// template <typename T> void QuickSort(T array[], int left, int right) {
//     // 只有一个元素的时候直接返回
//     if (right <= left)
//         return;
//     // 选择轴值
//     int privot = Partition(array, left, right);
//     // 左右递归调用
//     QuickSort(array, left, privot - 1);
//     QuickSort(array, privot + 1, right);
// }

// template <typename T> int Partition(T array[], int left, int right) {
//     int l = left;
//     int r = right;
//     T TempRecord = array[r]; // 保存当前轴值
//     while (l != r) {
//         while (array[l] <= TempRecord &&
//                r > l) // 从左边开始往右直到找到大于轴值索引的值位置
//             l++;
//         if (l < r) {
//             array[r] = array[l]; //
//             上述while退出可能是r<=l，所以需要先判断一下 r--;
//         }
//         while (array[r] >= TempRecord && r > l)
//             r--;
//         if (l < r) {
//             array[l] = array[r];
//             l++;
//         }
//     }
//     //
//     到此，左右索引指向相同的位置，此为止左边元素均小于等于轴值索引位置，右边均大于等于其
//     array[l] = TempRecord;
//     return l;
// }
// int SelectPrivot(int left, int right) { return (left + right) >> 1; }
// template <typename T> void QuickSort(T array[], int left, int right) {
//     // 只有一个元素的时候直接返回
//     if (right <= left)
//         return;
//     // 选择轴值
//     int privot = SelectPrivot(left, right);
//     // 将轴值和最后一个元素交换
//     std::swap(array[privot], array[right]);
//     // 找到左边小于等于 array[privot] 右边大于等于array[privot] 的位置
//     privot = Partition(array, left, right);
//     // 左右递归调用
//     QuickSort(array, left, privot - 1);
//     QuickSort(array, privot + 1, right);
// }

void Merge(int Array[], int TempArray[], int left, int right, int middle) {
    int i, j, index1, index2;
    // 将数组存放到临时数组
    for (j = left; j <= right; j++)
        TempArray[j] = Array[j];
    index1 = left;
    index2 = middle + 1;
    i = left;
    while (index1 <= middle && index2 <= right) {
        if (TempArray[index1] <= TempArray[index2])
            Array[i++] = TempArray[index1++];
        else
            Array[i++] = TempArray[index2++];
    }
    while (index1 <= middle)
        Array[i++] = TempArray[index1++];
    while (index2 <= right)
        Array[i++] = TempArray[index2++];
}
void MergeSort(int Array[], int TempArray[], int left, int right) {
    // Array为待排序的数组，left,right为两端
    int middle;
    if (left < right) // 序列中只有0或者1个记录，不用排序
    {
        middle = (left + right) / 2;               // 平分为两个子序列
        MergeSort(Array, TempArray, left, middle); // 对左半边排序
        MergeSort(Array, TempArray, middle + 1, right); // 对右半边排序
        Merge(Array, TempArray, left, right, middle);   // 归并
    }
}
template void QuickSort(int array[], int left, int right);

std::vector<int>& chooseSort(std::vector<int>& a)
{
    int min_index;
    for(int start_index = 0;start_index<a.size();start_index++)
    {
        int min_num = a[start_index];
        min_index = start_index;
        for(int index = start_index+1;index<a.size();index++)
        {
            if(a[index]<min_num)
            {
                min_num = a[index];
                min_index = index;
            }
        }
        std::swap(a[start_index],a[min_index]);
    }
    return a;
}

std::vector<double> bucketsort(std::vector<double> &data) {
    std::priority_queue<double> sortedBucket;
    std::map<int, std::priority_queue<double>> buck;
    std::vector<double> res;
  for (auto e : data) {
    int index = static_cast<int>(10 * e);
    if (buck.count(index)) {
      buck[index].push(-e);
    } else {
        std::priority_queue<double, std::vector<double>> buckSort;
      buckSort.push(-e);
      buck.insert(std::make_pair(index, buckSort));
    }
  }
  for (auto buckIndex : buck) {
    auto e = buckIndex.second;
    while (!e.empty()) {
      res.push_back(-e.top());
      e.pop();
    }
  }
  return res;
}

void countSort(int *a, int *b, int n) {
  int maxValue = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] > maxValue)
      maxValue = a[i];
  }
  int *count = new int[maxValue + 1]();
  //   统计元素的频率
  for (int i = 0; i < n; i++) {
    count[a[i]] += 1;
  }
  // 统计小于指定值出现的次数
  for (int i = 1; i <= maxValue; i++) {
    count[i] += count[i - 1];
  }
  for (int i = n - 1; i >= 0; i--) {
    b[count[a[i]] - 1] = a[i];
    count[a[i]] -= 1;
  }
  delete[] count;
>>>>>>> dev:cxx/algorithm/common/src/sortAlgorithm.cc
}
